#include "IDigraph.h"
#include "BfsVisitor.h"
#include "DfsVisitor.h"
#include "Algorithms.h"
#include "Testing.h"
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iostream>
#include <queue>

void setRandSeed(int new_seed)
{
	srand(new_seed);
}

std::string generateTests(int type_of_tests, int max_vertices_num, std::vector<Edge> &edges, int &vertices_num)
{
	std::string title = "";
	vertices_num = 1 + rand() % max_vertices_num;
	switch (type_of_tests)
	{
	case 0:
	{
		edges = generateAcyclic(vertices_num);
		title = "acyclic";
		break;
	}
	case 1:
	{
		title = "clique";
		edges = generateClique(vertices_num);
		break;
	}
	case 2:
	{
		edges = generateTree(vertices_num);
		title = "tree";
		break;
	}
	case 3:
	{
		edges = generateRandomized(vertices_num);
		title = "randomized";
		break;
	}
	case 4:
	{
		edges = generateFunctional(vertices_num);
		title = "functional";
		break;
	}
	}
	return title;
}

std::vector<Edge> generateClique(int vertices_num)
{
	std::vector<Edge> edges;
	for (int i = 0; i < vertices_num; i++)
		for (int j = i + 1; j < vertices_num; j++)
			edges.push_back(Edge(i, j)),
			edges.push_back(Edge(j, i));
	std::random_shuffle(edges.begin(), edges.end());
	return edges;
}

std::vector<Edge> generateFunctional(int vertices_num)
{
	std::vector<Edge> edges(vertices_num);
	for (size_t i = 0; i < edges.size(); i++)
		edges[i].begin = i, edges[i].end = rand() % vertices_num;
	std::random_shuffle(edges.begin(), edges.end());
	return edges;
}

std::vector<Edge> generateTree(int vertices_num)
{
	std::vector<Edge> edges(2 * (vertices_num - 1));
	std::vector<int> order(vertices_num);
	for (int i = 0; i < vertices_num; i++)
		order[i] = i;
	std::random_shuffle(order.begin(), order.end());
	for (int i = 1; i < vertices_num; i++)
	{
		edges[2 * i - 2].end = order[i], edges[2 * i - 2].begin = order[rand() % i];
		edges[2 * i - 1].begin = edges[2 * i - 2].end, edges[2 * i - 1].end = edges[2 * i - 2].begin;
	}
	std::random_shuffle(edges.begin(), edges.end());
	return edges;
}

std::vector<Edge> generateAcyclic(int vertices_num)
{
	std::vector<Edge> edges;
	if (vertices_num <= 1) return edges;
	std::vector<int> order(vertices_num);
	for (int i = 0; i < vertices_num; i++)
		order[i] = i;
	std::random_shuffle(order.begin(), order.end());
	int edges_num = rand() % (((vertices_num - 1) * vertices_num) / 2);
	for (int i = 0; i < edges_num; i++)
	{
		int begin = rand() % vertices_num;
		int end = rand() % (vertices_num - 1) + 1; end = (begin + end) % vertices_num;
		if (begin > end) std::swap(begin, end);
		edges.push_back(Edge(begin, end));
	}
	std::random_shuffle(edges.begin(), edges.end());
	return edges;
}

std::vector<Edge> generateRandomized(int vertices_num)
{
	std::vector<Edge> edges;
	if (vertices_num == 1) return edges;
	int edges_num = rand() % (((vertices_num - 1) * vertices_num));
	for (int i = 0; i < edges_num; i++)
	{
		int begin = rand() % vertices_num;
		int end = rand() % (vertices_num - 1); end = (begin + end + 1) % vertices_num;
		edges.push_back(Edge(begin, end));
	}
	std::random_shuffle(edges.begin(), edges.end());
	return edges;
}

void testGraphIntegrity(const std::unique_ptr<IDigraph> &graph, const std::vector<Edge> &edges, int vertices_num)
{
	if (vertices_num != graph->getNumberOfVertices())
	{
		std::cout << "Wrong number of vertices." << std::endl;
		return;
	}
	std::vector<std::vector<int> > neighbours(vertices_num, std::vector<int>(0));
	for (size_t i = 0; i < edges.size(); i++)
		neighbours[edges[i].begin].push_back(edges[i].end);
	for (int i = 0; i < vertices_num; i++)
	{
		std::vector<int> adjacent = graph->getIncidenceList(i);
		sort(neighbours[i].begin(), neighbours[i].end());
		neighbours[i].resize(unique(neighbours[i].begin(), neighbours[i].end()) - neighbours[i].begin());
		sort(adjacent.begin(), adjacent.end());
		adjacent.resize(unique(adjacent.begin(), adjacent.end()) - adjacent.begin());
		if (adjacent.size() != neighbours[i].size())
		{
			std::cout << "Wrong incidence list for vertex " << i << std::endl;
			return;
		}
		for (size_t j = 0; j < adjacent.size(); j++)
			if (adjacent[j] != neighbours[i][j])
			{
				std::cout << "Wrong incidence list for vertex " << i << std::endl;
				return;
			}
	}
}

void testProcessOrder(const std::unique_ptr<IDigraph> &graph, const std::vector<Edge> &order, int type)
{
	std::vector<bool> used(graph->getNumberOfVertices(), false);
	if (type == 0)
	{
		std::queue<int> vertex_process_queue;
		std::vector<bool> used(graph->getNumberOfVertices(), false);
		std::vector<std::vector<int> > adjacent(graph->getNumberOfVertices());
		for (int i = 0; i < graph->getNumberOfVertices(); i++)
			adjacent[i] = graph->getIncidenceList(i);
		for (size_t i = 0; i < order.size(); i++)
		{
			if (vertex_process_queue.empty())
			{
				if (used[order[i].begin])
				{
					std::cout << "Wrong processing order for bfs (start component from already used vertex)." << std::endl;
					return;
				}
				vertex_process_queue.push(order[i].begin);
				used[order[i].begin] = true;
			}
			while (!vertex_process_queue.empty() && adjacent[vertex_process_queue.front()].empty())
				vertex_process_queue.pop();
			int cur_vertex = (vertex_process_queue.empty() ? -1 : vertex_process_queue.front());
			if (cur_vertex != order[i].begin)
			{
				std::cout << "Wrong processing order for bfs (move from vertex not from the head of queue)." << std::endl;
				return;
			}
			if (!graph->isEdge(order[i]))
			{
				std::cout << "Wrong processing order for bfs (non-existent edge)." << std::endl;
				return;
			}
			if (adjacent[cur_vertex].size() == 0)
			{
				std::cout << "Wrong processing order for bfs (multiple processing of edge)." << std::endl;
				return;
			}
			if (!used[order[i].end])
			{
				used[order[i].end] = true;
				vertex_process_queue.push(order[i].end);
			}
			adjacent[cur_vertex].erase(std::find(adjacent[cur_vertex].begin(), adjacent[cur_vertex].end(), order[i].end));
			while (!vertex_process_queue.empty() && adjacent[vertex_process_queue.front()].empty())
				vertex_process_queue.pop();
		}
		for (int i = 0; i < graph->getNumberOfVertices(); i++)
			if (!adjacent[i].empty())
			{
				std::cout << "Wrong processing order for dfs (not all edges were processed)." << std::endl;
				return;
			}
	}
	if (type == 1)
	{
		std::vector<int> gray_stack;
		std::vector<bool> used(graph->getNumberOfVertices(), false);
		std::vector<std::vector<int> > adjacent(graph->getNumberOfVertices());
		for (int i = 0; i < graph->getNumberOfVertices(); i++)
			adjacent[i] = graph->getIncidenceList(i);
		for (size_t i = 0; i < order.size(); i++)
		{
			if (gray_stack.empty())
			{
				if (used[order[i].begin])
				{
					std::cout << "Wrong processing order for dfs (start component from already used vertex)." << std::endl;
					return;
				}
				gray_stack.push_back(order[i].begin);
				used[order[i].begin] = true;
			}
			if (gray_stack.back() != order[i].begin)
			{
				std::cout << "Wrong processing order for dfs (move from vertex not from the top of stack)." << std::endl;
				return;
			}
			if (!graph->isEdge(order[i]))
			{
				std::cout << "Wrong processing order for dfs (non-existent edge)." << std::endl;
				return;
			}
			if (adjacent[gray_stack.back()].size() == 0)
			{
				std::cout << "Wrong processing order for dfs (multiple processing of edge)." << std::endl;
				return;
			}
			int cur_vertex = gray_stack.back();
			if (!used[order[i].end])
			{
				used[order[i].end] = true;
				gray_stack.push_back(order[i].end);
			}
			adjacent[cur_vertex].erase(std::find(adjacent[cur_vertex].begin(), adjacent[cur_vertex].end(), order[i].end));
			while (!gray_stack.empty() && adjacent[gray_stack.back()].empty())
				gray_stack.pop_back();
		}
		for (int i = 0; i < graph->getNumberOfVertices(); i++)
			if (!adjacent[i].empty())
			{
				std::cout << "Wrong processing order for dfs (not all edges were processed)." << std::endl;
				return;
			}
	}
}

void testAlgorithms(const std::unique_ptr<IDigraph> &graph)
{
	int vertices_num = graph->getNumberOfVertices();
	if (vertices_num <= 1) return;
	std::vector<int> path, order;
	std::vector<bool> visited(vertices_num, false);
	double avg_bfs_time = 0.0, avg_dfs_time = 0.0, topsort_time = 0.0;
	time_t t_start;
	std::unique_ptr<BfsVisitor> bfs_solve(new BfsFindPath());
	std::unique_ptr<DfsVisitor> dfs_solve(new DfsTopologicalSort());
	for (int i = 0; i < 20; i++)
	{
		std::vector<bool> used(vertices_num, false); order.clear();
		int start = rand() % vertices_num, target = rand() % (vertices_num - 1) + 1;
		target = (target + start) % vertices_num;
		t_start = clock();
		bfs_solve->preInit();
		dynamic_cast<BfsFindPath*>(bfs_solve.get())->setTargetVertex(target);
		fill(visited.begin(), visited.end(), false);
		bfs_component(graph, start, bfs_solve, visited);
		avg_bfs_time += (double)(clock() - t_start) / CLOCKS_PER_SEC;
		path = dynamic_cast<BfsFindPath*>(bfs_solve.get())->getResultedPath();
		t_start = clock();
		dfs_solve.get()->preInit(graph);
		fill(visited.begin(), visited.end(), false);
		dfs_component(graph, start, dfs_solve, visited);
		avg_dfs_time += (double)(clock() - t_start) / CLOCKS_PER_SEC;
		if (dynamic_cast<DfsTopologicalSort*>(dfs_solve.get())->isVisited(target) ^ (path.size() != 0))
			std::cerr << "BFS and DFS results differ." << std::endl;
		for (size_t i = 0; i + 1 < path.size(); i++)
			if (!graph->isEdge(Edge(path[i], path[i + 1])))
			{
				std::cerr << "BFS has found non-existent path." << std::endl;
				break;
			}
		bfs(graph, bfs_solve);
		testProcessOrder(graph, dynamic_cast<BfsFindPath*>(bfs_solve.get())->getProcessOrder(), 0);
		dfs(graph, dfs_solve);
		testProcessOrder(graph, dynamic_cast<DfsTopologicalSort*>(dfs_solve.get())->getProcessOrder(), 1);
	}
	avg_bfs_time /= 20; avg_dfs_time /= 20;
	t_start = clock();
	bool has_cycle = true; topologicalSort(graph, order);
	topsort_time = (double)(clock() - t_start) / CLOCKS_PER_SEC;
	if (has_cycle)
		std::cout << "Graph has a loop." << std::endl;
	else
	{
		std::cout << "Graph has no loops." << std::endl;
		std::vector<int> adjacent, pos(vertices_num);
		for (int i = 0; i < vertices_num; i++)
			pos[order[i]] = i;
		bool bad_order = false;
		for (int i = 0; i < vertices_num && !bad_order; i++)
		{
			adjacent = graph->getIncidenceList(i);
			for (size_t j = 0; j < adjacent.size() && !bad_order; j++)
				if (pos[i] > pos[adjacent[j]]) bad_order = true;
		}
		if (bad_order)
			std::cerr << "Wrong order of topological sort." << std::endl;
	}
	std::cout.precision(4);
	std::cout << std::fixed << "Average time of DFS : " << avg_dfs_time << std::endl;
	std::cout << std::fixed << "Average time of BFS : " << avg_bfs_time << std::endl;
	std::cout << std::fixed << "Time of topological sort : " << topsort_time << std::endl;
}

void testBasic()
{
	std::vector<Edge> edges; int vertices_num = 0;
	for (int type = 0; type < 5; type++)
		for (int i = 0; i < 5; i++)
		{
			std::string title = generateTests(type, (type == 1 ? 500 : 2000), edges, vertices_num);
			title += (char)((i / 10) + (int)'0');
			title += (char)((i % 10) + (int)'0');
			std::unique_ptr<IDigraph> matrix_graph = std::move(std::unique_ptr<IMatrixGraph>(new IMatrixGraph(edges, vertices_num)));
			std::unique_ptr<IDigraph> list_graph = std::move(std::unique_ptr<IListGraph>(new IListGraph(edges, vertices_num)));
			std::unique_ptr<IDigraph> compact_graph = makeCompactGraph(edges, vertices_num);
			if (!(compact_graph->byteSize() <= list_graph->byteSize() && compact_graph->byteSize() <= matrix_graph->byteSize()))
				std::cout << "Wrong compactification result." << std::endl;

			if (title == "tree" || title == "functional")
				if (compact_graph->byteSize() > list_graph->byteSize())
					std::cout << "Wrong compactification of sparse graph." << std::endl;
			if (title == "clique")
				if (compact_graph->byteSize() > matrix_graph->byteSize())
					std::cout << "Wrong compactification of dense graph." << std::endl;

			std::cout << "Testing matrix graph on " << title << std::endl;
			testGraphIntegrity(matrix_graph, edges, vertices_num);
			testAlgorithms(matrix_graph);

			std::cout << std::endl << "Testing list graph on " << title << std::endl;
			testGraphIntegrity(list_graph, edges, vertices_num);
			testAlgorithms(list_graph);

			std::cout << std::endl;
		}
}

void testStronglyConnectedComponents(const std::unique_ptr<IDigraph> &graph, const std::vector<int> &components)
{
	std::vector<std::vector<bool> > connected(graph->getNumberOfVertices(), std::vector<bool>(graph->getNumberOfVertices(), false));
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
	{
		std::unique_ptr<DfsVisitor> dfs_solve(new DfsTopologicalSort());
		dfs_solve->preInit(graph);
		dfs_component(graph, i, dfs_solve, connected[i]);
	}
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
		for (int j = 0; j < graph->getNumberOfVertices(); j++)
			if ((connected[i][j] && connected[j][i]) ^ (components[i] == components[j]))
				std::cout << "Wrong components for vertices " << i << " and " << j << std::endl;
}

void testCondesedGraph(const std::unique_ptr<IDigraph> &graph, const std::unique_ptr<IDigraph> &condensed, const std::vector<int> &colors)
{
	int total_edges = 0;
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
	{
		std::vector<int> adjacent = graph->getIncidenceList(i);
		for (size_t j = 0; j < adjacent.size(); j++)
			if (colors[i] != colors[adjacent[j]])
				if (!condensed->isEdge(Edge(colors[i], colors[adjacent[j]])))
					std::cout << "Wrong edge in condensed graph between " << i << " and " << adjacent[j] << std::endl;
		total_edges += adjacent.size();
	}
}

void testTarjanOnGraph(const std::unique_ptr<IDigraph> &graph)
{
	std::unique_ptr<DfsVisitor> solution(new DfsTarjan);
	std::vector<int> colors = dynamic_cast<DfsTarjan*>(solution.get())->getVerticesColors(graph);
	testStronglyConnectedComponents(graph, colors);
	int vertex = rand() % graph->getNumberOfVertices();
	testCondesedGraph(graph, dynamic_cast<DfsTarjan*>(solution.get())->getCondesedGraph(graph), colors);
}

void testTarjan()
{
	std::vector<Edge> edges;
	int vertices_num;
	for (int i = 0; i < 10; i++)
	{
		generateTests(3, 1000, edges, vertices_num);
		std::unique_ptr<IDigraph> graph = makeCompactGraph(edges, vertices_num);
		testTarjanOnGraph(graph);
	}

	edges.clear();
	std::cout << "Test Tarjan`s algorithm on small graphs." << std::endl;
	testTarjanOnGraph(makeCompactGraph(edges, 1));
	for (int i = 2; i <= 5; i++)
	{
		int max_edges = i * (i - 1);
		for (int j = 0; j < (1 << max_edges); j++)
		{
			edges.clear();
			for (int k = 0; k < max_edges; k++)
				if ((j >> k) & 1)
					edges.push_back(Edge(k / (i - 1), (k % (i - 1) < i ? k % (i - 1) : k % (i - 1) + 1)));
			testTarjanOnGraph(makeCompactGraph(edges, i));
		}
	}
}

int check2SATSolution(const std::vector<int> &result, const std::vector<Edge> &edges, int variables)
{
	if (result[0] == -1) return -1;
	for (size_t j = 0; j < edges.size(); j++)
	{
		bool left_value = (edges[j].begin < variables) ^ (result[edges[j].begin % variables] == 1),
			right_value = (edges[j].end >= variables) ^ (result[edges[j].end % variables] == 1);
		if (!(left_value || right_value))
		{
			std::cout << "Wrong solution for 2-SAT." << std::endl;
			return 1;
		}
	}
	return 0;
}

void test2SAT()
{
	std::cout << "Test on likely solveable 2-SATs." << std::endl;
	for (int i = 0; i < 20; i++)
	{
		std::vector<Edge> edges(0);
		int variables = rand() % 1000 + 1;
		for (int j = 0; j < variables; j++)
		{
			int left = (rand() % 2 == 0 ? variables : 0) + (rand() % variables),
				right = (rand() % 2 == 0 ? variables : 0) + (rand() % variables);
			edges.push_back(Edge((left >= variables ? left - variables : left + variables), right));
			edges.push_back(Edge((right >= variables ? right - variables : right + variables), left));
		}
		std::unique_ptr<IDigraph> graph = makeCompactGraph(edges, 2 * variables);
		std::vector<int> result = solve2SAT(graph, variables);
		int check_result = check2SATSolution(result, edges, variables);
		if (check_result == 1)
			std::cout << "Wrong solution for 2-SAT." << std::endl;
	}
	std::cout << "Test on 2-SATs with no solution guaranteed." << std::endl;
	for (int i = 0; i < 20; i++)
	{
		std::vector<Edge> edges(0);
		int bad_variables = rand() % 1000 + 1, variables = 1000;
		std::vector<int> permutation(bad_variables);
		for (int j = 0; j < bad_variables; j++)
			permutation[j] = j;
		std::random_shuffle(permutation.begin(), permutation.end());
		for (int j = 0; j < bad_variables; j++)
			edges.push_back(Edge(permutation[j], permutation[(j + 1) % bad_variables])),
			edges.push_back(Edge(permutation[(j + 1) % bad_variables] + variables, permutation[j] + variables));
		for (int j = bad_variables; j < variables; j++)
		{
			int left = (rand() % 2 == 0 ? variables : 0) + (rand() % variables),
				right = (rand() % 2 == 0 ? variables : 0) + (rand() % variables);
			edges.push_back(Edge((left >= variables ? left - variables : left + variables), right));
			edges.push_back(Edge((right >= variables ? right - variables : right + variables), left));
		}
		std::unique_ptr<IDigraph> graph = makeCompactGraph(edges, 2 * variables);
		std::vector<int> result = solve2SAT(graph, variables);
		int check_result = check2SATSolution(result, edges, variables);
		if (check_result != -1)
			std::cout << "Wrong solution for non-solveable 2-SAT." << std::endl;
	}
}